package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         25,
		Discription: "k个一组反转链表",
		Level:       3,
		Labels: map[string]int{
			"链表":    1,
			"虚拟头指针": 1,
		},
	})
}

func ReverseKGroup(head *ds.ListNode, k int) *ds.ListNode {
	if head == nil || k == 1 {
		return head
	}

	// reverse
	// preNode: 要翻转的这一组链表的前一个节点
	// 返回： 下一个要翻转的一组链表的前一个节点（也是当前这一组链表翻转翻转前的第一个节点）
	reverse := func(preNode *ds.ListNode) *ds.ListNode {
		last := preNode
		i := 0
		//判断是否够k个，同时得到下一组链表的第一个节点，让当前组的第一个节点指向它
		for last.Next != nil && i < k {
			last = last.Next
			i++
		}
		if i < k {
			return nil
		}

		newHead := preNode.Next
		nextPre := newHead
		cur := newHead.Next
		//当前链表的第一个节点指向下一组链表的第一个节点
		newHead.Next = last.Next
		i = 1
		for cur != nil && i < k {
			next := cur.Next
			cur.Next = newHead
			newHead = cur
			cur = next
			i++
		}
		preNode.Next = newHead
		return nextPre
	}

	preHead := &ds.ListNode{
		Next: head,
	}
	pre := preHead
	for pre != nil {
		nextPre := reverse(pre)
		pre = nextPre
	}

	return preHead.Next
}
